package 重复的子字符串;

public class Solution2 {
    // 我们发现如果最长相等前后缀字串去掉重复部分，剩下的子字符串记为 s
    // 如果 s 的长度被够被 str 整除，那就说明这个字符串是重复构成的
    // s.length - next[s.length-1] 即表示了如果结果为true，那么最长前后缀长度在next[s.length-1]，且 s.length - next[s.length-1] 即为重复的字串s
    // 条件为： s.length % ( s.length - next[s.length-1] ) == 0

    // 补充：其实和我们方法一一样，只是不需要再统计有多少个0，1->n是不是递增的

    public boolean repeatedSubstringPattern(String s) {
        // 求next数组 => 寻找最长前后缀长度为多少
        int[] next = new int[s.length()];
        getNext(next, s);
        // 判断是否符合条件
        if( next[s.length()-1] != 0 && s.length() % ( s.length() - next[s.length()-1] ) == 0 )
            return true;
        else
            return false;
    }

    public void getNext(int[] next, String s) {
        int j = 0; // i为后缀末尾，j为前缀末尾
        next[0] = j;
        int length = s.length();
        for (int i = 1; i < length; i++) {
            // 当 s.charAt(i) != s.charAt(j) 时，需要回滚j(从next数组中向前寻找和next[i]相等的最长相等前后缀为多少)
            // next数组中数字的含义：以当前字符为前缀末尾的最长前后缀长度,包含当前字符
            char prefixEnd = s.charAt(j);
            char suffixEnd = s.charAt(i);
            // 不相等时，需要回退
            while (j > 0 && suffixEnd != prefixEnd) {
                j = next[j - 1];  // 不相等时回滚
                prefixEnd = s.charAt(j);
            }
            // 相等时
            if (suffixEnd == prefixEnd) j++; // 相等时则最长前后缀长度加一
            next[i] = j; // j既表示前缀末尾,又表示当前字符的最长前后缀长度
        }
    }

    public void getNext2(int[] next, String s) {
        int j = -1; // i是后缀的末尾,j是前缀的末尾
        next[0] = j;
        for (int i = 1; i < s.length(); i++) {
            // 不相等,回滚
            while (j > -1 && s.charAt(i) != s.charAt(j + 1)) j = next[j];
            // 相等时
            if (s.charAt(i) == s.charAt(j + 1)) j++;
            next[i] = j;
        }
    }
}
